﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Runtime.InteropServices.JavaScript.JSType;

public class Solution234
{
    public bool IsPalindrome(ListNode head)
    {

        //先找中间
        ListNode low = head;
        ListNode fast = head;
        while (fast!=null&&fast.next != null) { 
        
            low=low.next;
            fast=fast.next.next;

        }


        //先反转链表
        ListNode right= Reverse(low);//右边的比较长

        ListNode left = head;
        while (left != low) {

            if (left.val != right.val) { 
                return false;
            }
            left=left.next;
            right=right.next;
        
        
        }

        return true;




    }

    private ListNode Reverse(ListNode fast)
    {
        ListNode dummyHead = new ListNode();
        ListNode next =new ListNode();

        while (fast != null) {
            next = fast.next;
            fast.next = dummyHead.next;

            dummyHead.next = fast;
            fast = next;

        }
        return dummyHead.next;



    }
}
class Program234
{
    static void Main234()
    {

        ListNode root=new ListNode(1);

        root.next = new ListNode(2); 
        Solution234 sol = new Solution234();
    bool res=    sol.IsPalindrome(root);
        Console.WriteLine(res);



        ListNode list1 = new ListNode(1);

        for(int i = 0; i < 10; i++)
        {
            ListNode newNode = new ListNode(i);
            newNode.next = list1.next;
            list1.next = newNode;   

        }

        printListNode(list1);



    }

    private static void printListNode(ListNode head)
    {
        if (head != null) {
            printListNode(head.next);
            Console.WriteLine(head.val);//退出栈的时候才打印
        }
      
    }
}